package JZOffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Lw中
 * @date 2021/9/5 12:19
 */
public class Jz53 {

    // Jz53 I. 在排序数组中查找数字I
    public int search(int[] nums, int target) {

        // 方法一：循环遍历数组
//        int n = 0;
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int num : nums) {
//            if (num == target) {
//                map.put(num, ++n);
//            }
//        }
//        if (n == 0) {
//            return 0;
//        } else {
//            return map.get(target);
//        }

        // 方法二：二分查找
        return (helper(nums, target) - helper(nums, target - 1));

    }

    private int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }

}
